package com.str.list;
public class LinkedList implements List {
  // Each LinkedList value is an unbounded list whose elements are
  // objects.
  
// Inner class
  private static class SLLNode {
    Object data;
    SLLNode next;

    SLLNode() {}
    SLLNode(Object obj) { data = obj; }
    SLLNode(Object obj, SLLNode link) {  
      data = obj;
      next = link; 
    }

    public String toString()
    { return data.toString(); }
  }
  
  private SLLNode first, last;
  private int count;

// Constructor ...
  public LinkedList() {
  // Construct a list, initially empty.
    clear();
  }

// Modifiers
  public final void clear() {
  // Make this list empty.
    first = last = null;
    count = 0;
  }

  public void add(int i, Object val) {
  // Add x as the element with index i in this list.
    if (i < 0 || i > count)
      throw new IndexOutOfBoundsException();
    SLLNode temp = new SLLNode(val, null);
    if (i == 0) {
      temp.next = first;
      first = temp;
    }
    else {
      SLLNode prior = setPos(i-1);
      temp.next = prior.next;
      prior.next = temp;
    }
    if (temp.next == null)
      last = temp;
    count++;
  }

  public void add(Object val) {
  // Add x after the last element of this list.
    SLLNode temp = new SLLNode(val, null);
    if (first == null)
      first = temp;
    else
      last.next = temp;
    last = temp;
    count++;
  }

  public Object remove(int i) {
  // Remove and return the element with index i in this list, or return null
  // if there is no such element.
    if (i < 0 || i >= count)
      throw new IndexOutOfBoundsException();
    Object val;
    if (i == 0) {
      val = first.data;   
      first = first.next;
      if (first == null) last = null;
    } 
    else {
      SLLNode prior = setPos(i-1);
      SLLNode curr = prior.next;
      val = curr.data;
      prior.next = curr.next;
      if (curr == last) last = prior;
    }
    count--;
    return val;
  }

// Accessors 
  public boolean isEmpty() {
  // Return true if and only if this list is empty.
    return first == null;
  }

  public int size() {
  // Return this list's length.
    return count;
  }
  
  public Object getValue(int i) {
  // Return the element with index i in this list, or null if there is
  // no such element.
    if (i < 0 || i >= count)
      throw new IndexOutOfBoundsException();
    SLLNode curr = setPos(i);
    return curr.data;
  }
  
  public int indexOf(Object val) {
  	int i = 0;
    for (SLLNode curr = first; curr != null; curr = curr.next, i++)
      if (val.equals(curr.data))
        return i;
    return -1;
  }
    
// Auxiliary methods
  private SLLNode setPos(int i) {
  // Return a link to the node containing the element with index i in
  // this list.
    SLLNode curr = first;
    for (int j = 0; j < i; j++)
      curr = curr.next;
    return curr;
  }

  public String toString() {
    String buf = new String("[ ");
    for (SLLNode curr = first; curr != null; curr = curr.next) {            
      if (curr != first) buf += ", ";
      buf += curr.data;
    }
    buf += " ]";
    return buf;
  }
}
